package tree

import (
	"sort"
)

// m阶B+树表示了内部结点最多有m-1个关键字（或者说内部结点最多有m个子树）
// 阶数m同时限制了叶子结点最多存储m-1个记录

// 内部结点中的key都按照从小到大的顺序排列
// 对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它

// 每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接
type Value string
type Key int
type BPlusTree struct {
	Root *BPlushTreeNode
	Ptr  *BPlushTreeNode
}

//新建一棵空树时初始化一个根节点
func (b *BPlusTree) Initialize() {
	node := MallocTreeNode(true, nil)
	b.Ptr = node
	b.Root = node
}

func (b *BPlusTree) Insert(key Key, value Value) (success bool) {
	//查找需要插入的节点
	position := FindInsertPosition(b.Root, key)
	//向这个叶子结点插入记录
	position.insertKeyValue(key, value)
	//插入后，若当前结点key的个数小于等于m-1，则插入结束
	if position.KeyNum <= M-1 {
		return true
	}
	//否则将这个叶子结点分裂成左右两个叶子结点,并将M/2指向父节点
	b.recursiveSplitNode(position)
	return true
}

func (b *BPlusTree) recursiveSplitNode(position *BPlushTreeNode) *BPlushTreeNode {
	if position.KeyNum <= M-1 {
		return position
	}
	if position.isLeaf {
		//新建一个右节点节点，用于分裂
		rNode := MallocTreeNode(true, position.parent)
		//左叶子结点包含前m/2个记录，右结点包含剩下的记录
		//将左节点的M/2 - M的位置上的key和value复制给右节点
		copy(rNode.Keys[:M-M/2], position.Keys[M/2:])
		copy(rNode.LeafNode.datas[:M-M/2], position.LeafNode.datas[M/2:])
		rNode.KeyNum += M - M/2
		position.KeyNum -= M - M/2
		//清空左m/2以后的key指针和data数据
		for i := position.KeyNum; i < len(position.Keys); i++ {
			position.Keys[i] = Key(INT_MIN)
			position.LeafNode.datas[i] = Empty_Value
		}
		//这是一个根节点
		if position.parent == nil {
			//此时由于是根节点分裂需要新建一个根节点
			root := MallocTreeNode(false, nil)
			root.insertKeyValue(rNode.Keys[0], Empty_Value)
			root.Children[0] = position
			root.Children[1] = rNode
			b.Root = root
			position.parent = root
			rNode.parent = root
			//叶子节点next指针赋值
			rNode.LeafNode.Next = position.LeafNode.Next
			position.LeafNode.Next = rNode
			b.Ptr = position
			return root
		}
		//是叶子节点，且不是根节点
		//将第所以为[m/2]的记录的key进位（不删除）到父结点中（父结点一定是索引类型结点）
		position.parent.insertKeyValue(rNode.Keys[0], Empty_Value)
		//将当前结点的指针指向父结点,insertNode中已经有指向
		position.parent.insertNode(position, rNode)
		//叶子节点next指针赋值
		rNode.LeafNode.Next = position.LeafNode.Next
		position.LeafNode.Next = rNode
		return b.recursiveSplitNode(position.parent)
	} else {
		//左索引结点包含前m/2个key
		//右结点包含m-m/2个key，将第索引为[m/2]移位(删除)到父结点中，移位到父结点的key左孩子指向左结点
		//新建一个索引节点用于分裂
		rNode := MallocTreeNode(false, position.parent)
		beAdjustKey := position.Keys[M/2]
		//分割key,左节点包含m/2个，右节点包含m - m/2个
		copy(rNode.Keys[:M-M/2], position.Keys[M/2:])
		rNode.KeyNum += M - M/2
		position.KeyNum -= M - M/2
		//分出去的key置空
		for i := position.KeyNum; i < len(position.Keys); i++ {
			position.Keys[i] = Key(INT_MIN)
		}
		//分割孩子,且将孩子的parent重新指向
		copy(rNode.Children[:], position.Children[M/2+1:])
		for i := 0; i < rNode.KeyNum; i++ {
			rNode.Children[i].parent = rNode
		}
		//将position被分割的孩子清零
		for i := M/2 + 1; i < len(position.Children); i++ {
			position.Children[i] = nil
		}
		//如果是root节点需要分裂
		if position.parent == nil {
			//新建一个root节点
			b.Root = MallocTreeNode(false, nil)
			rNode.parent = b.Root
			position.parent = b.Root
			b.Root.Children[0] = position
			b.Root.Children[1] = rNode
			//将第索引为[M/2]的Key（右节点第一个）移位动到父结点中（父结点一定是索引类型结点）
			beAdjustKey, _ = rNode.removeKey(beAdjustKey)
			position.parent.insertKeyValue(beAdjustKey, Empty_Value)
			//将当前结点的指针指向父结点,insertNode中已经有指向
			return b.recursiveSplitNode(position.parent)
		}
		//当前索引节点非root节点
		//将第索引为(M-1)/2的Key移位到父结点中（父结点一定是索引类型结点）
		beAdjustKey, _ = rNode.removeKey(beAdjustKey)
		position.parent.insertKeyValue(beAdjustKey, Empty_Value)
		//将当前结点的指针指向父结点,insertNode中已经有指向
		position.parent.insertNode(position, rNode)
		return b.recursiveSplitNode(position.parent)
	}
}

// FindInsertPosition 找到需要插入的叶子节点
func FindInsertPosition(root *BPlushTreeNode, key Key) *BPlushTreeNode {
	curNode := root
	if root.KeyNum < M && root.isLeaf {
		return root
	}
	for !curNode.isLeaf {
		childIdx := 0
		found := false
		for i := 0; i < curNode.KeyNum; i++ {
			if key < curNode.Keys[i] {
				found = true
				childIdx = i
				break
			}
		}
		if !found {
			childIdx = curNode.KeyNum
		}
		curNode = curNode.Children[childIdx]
	}
	return curNode
}

func (b *BPlusTree) FindData(key Key) (Value, bool) {
	curNode := b.Root
	for !curNode.isLeaf {
		childIdx := sort.Search(curNode.KeyNum, func(i int) bool {
			return curNode.Keys[i] > key
		})
		curNode = curNode.Children[childIdx]
	}
	//root是叶子节点
	if curNode != nil {
		dataIdx := sort.Search(curNode.KeyNum, func(i int) bool {
			return curNode.Keys[i] >= key
		})
		if dataIdx == curNode.KeyNum {
			return Empty_Value, false
		}
		if curNode.Keys[dataIdx] == key {
			return curNode.LeafNode.datas[dataIdx], true
		}
		return Empty_Value, false
	}
	return Empty_Value, false
}

/*
如果叶子节点中没有相应的key, 则删除失败. 否则执行下面的步骤.
1.删除叶子节点中对应的key. 删除后若节点的key的个数大于等于Math.ceil(m)/2 - 1, 删除操作结束, 否则执行第二步.
2.若兄弟节点key有富余（大于Math.ceil(m)/2 – 1），向兄弟结点借一个记录，同时用借到的key替换父结（指当前结点和兄弟结点共同的父结点）点中的key，删除结束。否则执行第3步。
3.若兄弟结点中没有富余的key,则当前结点和兄弟结点合并成一个新的叶子结点，并删除父结点中的key（父结点中的这个key两边的孩子指针就变成了一个指针，正好指向这个新的叶子结点），将当前结点指向父结点（必为索引结点），执行第4步
4.若索引结点的key的个数大于等于Math.ceil(m)/2 – 1，则删除操作结束。否则执行第5步.
5.若兄弟结点有富余，父结点key下移，兄弟结点key上移，删除结束。否则执行第6步
6.当前结点和兄弟结点及父结点下移key合并成一个新的结点。将当前结点指向父结点，重复第4步。注意，通过B+树的删除操作后，索引结点中存在的key，不一定在叶子结点中存在对应的记录。
*/
func (b *BPlusTree) Remove(key Key) bool {
	beRemoveDataNode := FindInsertPosition(b.Root, key)
	if beRemoveDataNode == nil {
		return false
	}
	removedKey, _ := beRemoveDataNode.removeKey(key)
	if removedKey == Key(INT_MIN) {
		return false
	}
	// 删除成功,判断叶子节点的KeyValue个数是否大于等于(M-1)/2,或者当前节点是根节点则返回
	if beRemoveDataNode.KeyNum >= (M-1)/2 || beRemoveDataNode.parent == nil {
		return true
	}
	// 删除成功后关键字个数少于(M-1)/2
	// 查看兄弟节点是否有剩余
	sibling, parentKey, right := findSibling(beRemoveDataNode.parent, beRemoveDataNode)
	// 如果兄弟节点有节点可以借出
	if sibling.KeyNum > (M-1)/2 {
		// 向兄弟节点借一个数据过来，并用借过来的数据去替换(不删除叶子节点数据)掉共同父节点中的key
		var borrowKey Key
		var value Value
		if right {
			borrowKey, value = removedLeftKey(sibling) // TODO 左兄弟节点移除最右key右兄弟节点移除最左key
		} else {
			borrowKey, value = removedRightKey(sibling) // TODO 左兄弟节点移除最右key右兄弟节点移除最左key
		}
		_ = beRemoveDataNode.insertKeyValue(borrowKey, value)
		// TODO 当前是叶子节点 需要替换（不删除叶子节点）共有父节点的key
		// 1.如果向右节点借的，那么使用右节点的移除key后的,第一个leftKey上移（不删除）,替换父节点key
		beRemoveDataNode.parent.removeKey(parentKey)
		if right {
			newLeftKey := sibling.Keys[0]
			beRemoveDataNode.parent.insertKeyValue(newLeftKey, value)
			return true
		}
		// 2.如果向左节点借的，那么直接使用借过来的的key上移（不删除）,替换父节点key
		beRemoveDataNode.parent.insertKeyValue(borrowKey, Empty_Value)
		return true
	}
	// 兄弟节点无富于数据,合并兄弟节点，并删除父节点key
	mergeLeafSibling(beRemoveDataNode, sibling, parentKey, right)
	recurAdjustNoLeafNode(beRemoveDataNode.parent)
	return true
}

// 递归调整非叶子节点的key数量
func recurAdjustNoLeafNode(currNode *BPlushTreeNode) {
	// 判断关键字数量是否合法
	if currNode == nil || currNode.parent == nil || currNode.KeyNum >= (M-1)/2 {
		return
	}
	sibling, parentKey, right := findSibling(currNode.parent, currNode)
	// 如果兄弟节点有节点可以借出
	if sibling.KeyNum > (M-1)/2 {
		// 兄弟节点有富于，父节点key下移，兄弟节点的key上移
		var adjustKey Key
		var moveChild *BPlushTreeNode
		if right {
			// 右兄弟的最左child移动到当前节点
			moveChild = sibling.Children[0]
			adjustKey, _ = removedLeftKey(sibling)
			copy(sibling.Children[0:], sibling.Children[1:])
		} else {
			// 左兄弟的最右边child移动到当前节点
			moveChild = sibling.Children[sibling.KeyNum]
			adjustKey, _ = removedRightKey(sibling)
			sibling.Children[sibling.KeyNum+1] = nil
		}

		// 父节点下移
		currNode.parent.removeKey(parentKey)
		currNode.insertKeyValue(parentKey, Empty_Value)
		// 兄弟节点上移
		currNode.parent.insertKeyValue(adjustKey, Empty_Value)
		// 兄弟节点的一个child移动到当前节点
		if right {
			// 如果是左兄弟节点则直接将该child追加到当前节点最后
			currNode.Children[currNode.KeyNum] = moveChild
		} else {
			// 如果是右兄弟节点则插入children头部
			copy(currNode.Children[1:], currNode.Children[0:])
			currNode.Children[0] = moveChild
		}
		moveChild.parent = currNode
		return
	}
	// 若没有富于，当前节点和兄弟节点以及父节点key合并成一个新节点，并递归判断新父节点是否合法
	// 1.移动兄弟节点的子节点
	if right {
		currNode.Children = append(currNode.Children[0:currNode.KeyNum+1], sibling.Children[0:sibling.KeyNum+1]...)
	} else {
		currNode.Children = append(sibling.Children[0:sibling.KeyNum+1], currNode.Children[0:currNode.KeyNum+1]...)
	}

	for len(currNode.Children) < M+1 {
		currNode.Children = append(currNode.Children, nil)
	}
	// 2.移动兄弟节点key
	for _, key := range sibling.Keys {
		if key == Key(INT_MIN) {
			break
		}
		currNode.insertKeyValue(key, Empty_Value)
	}
	// 修改子节点指向
	for _, child := range currNode.Children {
		if child == nil {
			break
		}
		child.parent = currNode
	}
	// 3.删除兄弟节点
	for i, child := range sibling.parent.Children {
		if sibling == child {
			copy(sibling.parent.Children[i:], sibling.parent.Children[i+1:])
			break
		}
	}
	for len(currNode.parent.Children) < M+1 {
		currNode.parent.Children = append(sibling.parent.Children, nil)
	}
	// 父节点key下移
	currNode.parent.removeKey(parentKey)
	currNode.insertKeyValue(parentKey, Empty_Value)
	// 如果是父节点是根节点
	if currNode.parent.parent == nil && currNode.parent.KeyNum == 0 {
		currNode.parent = nil
	}
	recurAdjustNoLeafNode(currNode.parent)
}

func mergeLeafSibling(node *BPlushTreeNode, sibling *BPlushTreeNode, parentKey Key, isRightSibling bool) {
	if !node.isLeaf || !sibling.isLeaf {
		panic(" sibling or node not leaf")
	}
	// 1.合并叶子节点key
	if isRightSibling {
		for i, key := range sibling.Keys {
			if key == Key(INT_MIN) {
				break
			}
			node.insertKeyValue(key, sibling.LeafNode.datas[i])
		}
	} else { // 合并到左兄弟
		for i, key := range node.Keys {
			if key == Key(INT_MIN) {
				break
			}
			sibling.insertKeyValue(key, node.LeafNode.datas[i])
		}
	}
	// 2.接替叶子兄弟节点的next
	if isRightSibling {
		node.LeafNode.Next = sibling.LeafNode.Next
	} else {
		// 左兄弟
		sibling.LeafNode.Next = node.LeafNode.Next
	}
	// 3. 删除兄弟节点
	needRemove := sibling
	if !isRightSibling {
		needRemove = node
	}
	for i, child := range sibling.parent.Children {
		if needRemove == child {
			copy(needRemove.parent.Children[i:], needRemove.parent.Children[i+1:])
			if len(sibling.parent.Children) < M {
				needRemove.parent.Children = append(needRemove.parent.Children, nil)
			}
			break
		}
	}
	// 删除父节点key
	needRemove.parent.removeKey(parentKey)
	if needRemove.parent.KeyNum == 0 {
		needRemove.parent.Children[0].parent = nil
	}
}

// 移除node节点的最右边的key
func removedRightKey(node *BPlushTreeNode) (Key, Value) {
	removedKey := node.Keys[node.KeyNum-1]
	copy(node.Keys[node.KeyNum-1:], node.Keys[node.KeyNum:])
	// 如果是叶子节点则同时移除value
	var removedValue = Empty_Value
	if node.isLeaf {
		removedValue = node.LeafNode.datas[node.KeyNum-1]
		copy(node.LeafNode.datas[node.KeyNum-1:], node.LeafNode.datas[node.KeyNum:])
	}
	if len(node.Keys) < M {
		node.Keys = append(node.Keys, Key(INT_MIN))
		if node.isLeaf && len(node.LeafNode.datas) < M {
			node.LeafNode.datas = append(node.LeafNode.datas, Empty_Value)
		}
	}
	node.KeyNum--
	return removedKey, removedValue
}

// 移除node节点的左边的key
func removedLeftKey(node *BPlushTreeNode) (Key, Value) {
	removedKey := node.Keys[0]
	copy(node.Keys[0:], node.Keys[1:])
	// 如果是叶子节点则同时移除value
	var removedValue = Empty_Value
	if node.isLeaf {
		removedValue = node.LeafNode.datas[0]
		copy(node.LeafNode.datas[0:], node.LeafNode.datas[1:])
	}
	if len(node.Keys) < M {
		node.Keys = append(node.Keys, Key(INT_MIN))
		if node.isLeaf && len(node.LeafNode.datas) < M {
			node.LeafNode.datas = append(node.LeafNode.datas, Empty_Value)
		}
	}
	node.KeyNum--
	return removedKey, removedValue
}

// 根据传入的父节点查找postNode的兄弟节点，优先查找右边的兄弟,返回sibling以及parent中两兄弟对应的key
func findSibling(parent *BPlushTreeNode, prePosition *BPlushTreeNode) (sibling *BPlushTreeNode, key Key, right bool) {
	right = true
	if parent.isLeaf {
		return nil, Key(INT_MIN), right
	}
	siblingIdx := 0
	keyIdx := 0
	for i, child := range parent.Children {
		if child == prePosition {
			siblingIdx = i + 1
			break
		}
	}
	if parent.Children[siblingIdx] != nil {
		keyIdx = siblingIdx - 1
	}
	if parent.Children[siblingIdx] == nil {
		right = false
		siblingIdx -= 2
		keyIdx = siblingIdx
		if siblingIdx == 0 {
			keyIdx = siblingIdx
		}
	}
	return parent.Children[siblingIdx], parent.Keys[keyIdx], right
}
